package leetcode.链表;

/**
 * 两两交换链表中的节点
 *
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 解答
 * 双指针法：1=>2=>3=>4
 * 例如：第一根指针指向第一个元素：1、第二个指针指向第二个元素：2，
 * 交换这个两根指针指向的元素：2=>1=>3=>4
 * 然后，第一根指针跳跃一个元素，指向下一个元素：3，第二根指针还是指向第一根元素的下一个元素：4
 * 直到当前元素的下一个为空，终止循环
 * TODO 再来一次
 */
public class Test24两两交换链表中的节点 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 链表不会变短，只是指针在移动，剩下的链表在变短
     * 需要指向链表头部的指针
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }
        // head: 1=>2=>3=>4
        ListNode ans = new ListNode(0);
        ans.next = head; // 0=>1=>2=>3=>4

        head = ans; // head: 0=>1=>2=>3=>4
        while (head.next != null && head.next.next != null) {
            // n1: 1=>2=>3=>4    n2: 2=>3=>4
            ListNode n1 = head.next, n2 = head.next.next;

            // 把头后面的n1变成n2
            head.next = n2; // head: 0=>2=>3=>4
            // 然后把n1放到n2的位置（到此位置n1.n2位置交换结束）
            n1.next = n2.next;  // n1: 1=>3=>4
            // 最后把n1衔接到n2的尾巴上
            n2.next = n1; // n2: 2=>1=>3=>4

            // 这一部分比较巧妙，利用n1交换到n2的位置后立刻将指针跳跃一次
            head = n1; // head: 1=>3=>4
        }

        return ans.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;

        ListNode ans = swapPairs(l1.next);
        while (ans != null) {
            System.out.print(ans.val);
            ans = ans.next;
        }
    }
}
